package com.yvon.service.demo.algorithm.stack;

import java.util.Stack;

/**
 * @author : Yvon
 * @since : 2022-04-26
 */
public class TreePreOrder {

    public static void main(String[] args) {
        //创建6个节点
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        //根据图上的节点关系用代码表示出来
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.right = node6;
        preorderTraversal(node1);
    }

     static void preOrderRecursively(TreeNode tree) {
        if (tree == null) {
            return;
        }
        System.out.println(tree.value);
        preOrderRecursively(tree.left);
        preOrderRecursively(tree.right);
    }

    static void preorderTraversal(TreeNode root) {
        if(root == null)
            return;
        // 用来暂存节点的栈
        Stack<TreeNode> treeNodeStack = new Stack<>();
        // 新建一个游标节点为根节点
        TreeNode node = root;
        // 当遍历到最后一个节点的时候，无论它的左右子树都为空，并且栈也为空
        // 所以，只要不同时满足这两点，都需要进入循环
        while (node != null || !treeNodeStack.isEmpty()) {
            // 若当前考查节点非空，则输出该节点的值
            // 由考查顺序得知，需要一直往左走
            while (node != null) {
                System.out.print("输出节点：" + node.value);
                // 为了之后能找到该节点的右子树，暂存该节点
                treeNodeStack.push(node);
                node = node.left;
            }
            // 一直到左子树为空，则开始考虑右子树
            // 如果栈已空，就不需要再考虑，弹出栈顶元素，将游标等于该节点的右子树
            if (!treeNodeStack.isEmpty()) {
                node = treeNodeStack.pop();
                node = node.right;
            }
        }

    }


    static void middleOrderRecursively(TreeNode tree) {
        if (tree == null) {
            return;
        }
        middleOrderRecursively(tree.left);
        System.out.println(tree.value);
        middleOrderRecursively(tree.right);
    }

    static void postOrderRecursively(TreeNode tree) {
        if (tree == null) {
            return;
        }
        postOrderRecursively(tree.left);
        postOrderRecursively(tree.right);
        System.out.println(tree.value);
    }


    public static void add() {
        int i1 = 10;
        i1 ++;
        System.out.println(i1); // 11

        int i2 = 10;
        ++ i2;
        System.out.println(i2); // 11

        int i3 = 10;
        int i4 = i3++;
        System.out.println(i3); // 11
        System.out.println(i4); // 10

        int i5 = 10;
        int i6 =  ++i5;
        System.out.println(i5); // 11
        System.out.println(i6); // 11

        int i7 = 10;
        i7 = i7++;
        System.out.println(i7); // 10

        int i8 = 10;
        i8 = ++i8;
        System.out.println(i8); // 11

        int i9 = 10;
        int i10 = i9++ + ++i9; // 10 + 12
        System.out.println(i9); // 12
        System.out.println(i10); // 22
    }
}
